/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2023-06-28
 * Time: 22:06
 */
public class Solution {
    /**
     *  方法一 : dp + 双向遍历
     *  三个递增的, 说明 nums[i] 左边存在比他小的, 右边存在比他大的
     *  第一遍 dp 存 dp[i] 前 i+1 个 中最小的值
     *  第二遍 dp 存 dp[i] 之后的 最大值
     *  最后双向遍历
     * @param nums
     * @return
     */
    public boolean increasingTriplet(int[] nums) {
        int len = nums.length;
        int[] dp1 = new int[len];
        int[] dp2 = new int[len];
        dp1[0] = nums[0];
        dp2[len-1] = nums[len-1];
        // 第一遍 dp 存 dp[i] 前 i+1 个 中最小的值
        for (int i = 1;i < len;i++) {
            dp1[i] = Math.min(nums[i], dp1[i-1]);
        }
        // 第二遍 dp 存 dp[i] 之后的 最大值
        for (int i = len-2;i >= 0;i--) {
            dp2[i] = Math.max(nums[i], dp2[i+1]);
        }
        // 最后双向遍历
        for (int i = 1;i < len-1;i++) {
            if (nums[i] > dp1[i-1] && nums[i] < dp2[i+1]) {
                return true;
            }
        }
        return false;
    }


    /**
     *  方法二: 贪心
     *  first 记录最小的, second 记录比 first 大的
     *  若 nums[i] > second -> true
     *  first < nums[i] < second -> 更新 second
     *  nums[i] < first -> 更新 first
     *  如果出现 second 在左, first在右的情况也没事,
     *  因为 不管 second 在哪, second 左边总是存在比 second 小的值
     * @param nums
     * @return
     */
    public boolean increasingTriplet2(int[] nums) {
        int len = nums.length;
        if (len < 3) {
            return false;
        }
        int first = nums[0];
        int second = Integer.MAX_VALUE;
        for (int i = 1;i < len;i++) {
            // 若 nums[i] > second -> true
            if (nums[i] > second) {
                return true;
            } else if (nums[i] > first) {
                // first < nums[i] < second -> 更新 second
                second = nums[i];
            } else if (nums[i] < first) {
                // nums[i] < first -> 更新 first
                // 如果出现 second 在左, first在右的情况也没事,
                // 因为 不管 second 在哪, second 左边总是存在比 second 小的值
                first = nums[i];
            }
        }
        return false;
    }
}
